package Arrays;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _581_ShortestUnsortedContinuousSubarray {
    //situation : 1:already sort,2:have the same number[3,2,2,2,],3:[2,3,3,2]
    //4:many same number,5:[1,2,4,5,3],6:[1,2,3,3,3],7:[1,3,2,3,3] failed
    public int findUnsortedSubarray(int[] nums) {
        int[] copy = new int[nums.length];
        copy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(copy);
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();
        Map<Integer,Integer> endMap = new HashMap<Integer,Integer>();
        for(int i=0;i<copy.length;i++) {
            if (!map.containsKey(copy[i])) {
                map.put(copy[i], i);
            } else {
                endMap.put(copy[i], i);
            }
        }
        int begin=Integer.MAX_VALUE,end=Integer.MIN_VALUE;
        System.out.println(map.toString());
        for(int i=0;i<nums.length;i++) {
            int pos = map.get(nums[i]);
            if (!endMap.containsKey(nums[i])) {
                if (i < pos) {
                    if (end < pos) {
                        end = pos;
                    }
                } else if (i > pos) {
                    if (begin > pos) {
                        begin = pos;
                    }
                }
            } else {
                int endPos = endMap.get(nums[i]);
                if (nums[i] == copy[i] && nums[endPos] == copy[endPos]) {
                }else{
                    if (i < endPos) {
                        if (end < endPos) {
                            end = endPos;
                        }
                    } else if (i > pos) {
                        if (begin > pos) {
                            begin = pos;
                        }
                    }
                }
            }
        }
        if (begin != Integer.MAX_VALUE && end != Integer.MIN_VALUE) {
            return end - begin + 1;
        } else {
            return 0;
        }
    }

    //reference solution
    public int findUnsortedSubarray1(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }

    /*public int findUnsortedSubarray(int[] nums) {
        int start = -1,end = -1;
        boolean started = false;
        boolean larger = false;
        boolean equal = false;
        int temp = 0;
        for(int i=0;i<nums.length-1;i++) {
            if (nums[i] > nums[i + 1]) {
                if (!started) {
                    start = i;
                    end = i + 1;
                    started = true;
                    larger = true;
                } else {
                    end = i + 1;
                    larger = true;
                }
            } else if (nums[i] == nums[i + 1]) {
                if (larger) {
                    end = i + 1;
                } else {
                    int pos = i;
                    while (pos < (nums.length - 1) && nums[pos]==nums[pos+1]) {
                        pos++;
                    }
                    System.out.println(pos);
                    if (pos < (nums.length - 1)&& nums[pos] > nums[pos + 1]) {
                        if (!started) {
                            start = i;
                            started = true;
                        } else {
                            end = pos+1;
                        }
                    }
                }
            } else {
                larger = false;
            }
        }
        return (end - start)==0?0:end-start + 1;
    }*/

}
